8709. Валя и письмо

Валя устала от социальных сетей и решила написать своей подруге Саше письмо на прямоугольном листе бумаге. Длины сторон листа равны n и m сантиметрам. Потом она нашла конверт прямоугольной формы, длины сторон которого равны h и w сантиметрам.

К сожалению, письмо может не помещаться в конверт, в этом случае Вале придется несколько раз сложить письмо. За одно действие Валя может сложить письмо пополам по вертикали или по горизонтали.

После того, как Валя, при необходимости, несколько раз сложит письмо пополам, она планирует положить его в конверт. Валя – очень аккуратная девочка, она всегда кладёт письмо в конверт таким образом, чтобы его стороны были параллельны сторонам конверта. Письмо помещается в конверт, если длины его стороны не больше длин соответствующих сторон конверта. Прежде чем положить письмо в конверт, Валя может повернуть его на 90 градусов. Например, если длины сторон письма равны 10 и 20 сантиметрам, а длины сторон конверта равны 20 и 10 сантиметрам, Вале не нужно сгибать письмо, она может повернуть его на 90 градусов и положить в конверт.

Валя не хочет, чтобы письмо получилось очень мятым, поэтому она хочет сложить письмо пополам минимальное число раз. Помогите ей выяснить, какое минимальное число раз ей придется сложить письмо перед тем, как она сможет положить его в конверт.

Вход. Первая строка содержит четыре целых числа n, m, h и w (1 ≤ n, m, h, w ≤ 10¹⁸) – длины сторон письма и конверта соответственно.

Выход. Выведите одно число – какое минимальное число раз Вале придётся сложить письмо, чтобы она могла положить его в конверт.

Пример входа 1	Пример выхода 1
10 20 20 10	0
Пример входа 2	Пример выхода 2
3 3 2 2	2

РЕШЕНИЕ

рекурсия

Анализ алгоритма

Решим сначала задачу когда размеры листа равны n и m, а размеры конверта h и w. Для этого реализуем функцию solve(n, m, h, w). Затем провернем лист на 90 градусов и решим задачу для листа m * n и конверта h * w, вызвав функцию solve(m, n, h, w). Наименьшее среди этих значений и будет ответом.

Рассмотрим реализацию solve(n, m, h, w).

· Если h ≥ n и w ≥ m, то письмо помещается в конверт и возвращаем 0 (лист складывать не надо);

· Если h < n, то письмо следует свернуть пополам по стороне длины n. Для избежания работы с действительными числами, вместо деления n на 2 (n / 2 может стать действительным), мы увеличим размер h конверта в 2 раза. Количество изгибов письма станет равным

1 + solve(n, m, 2 * h, w)

· При w < m увеличим размер w конверта в 2 раза. Количество изгибов письма станет равным

1 + solve(n, m, h, 2 * w)

Пример

Рассмотрим второй тест. Количество изгибов равно

solve(3, 3, 2, 2) = 1 + solve(3, 3, 4, 2) = 1 + 1 + solve(3, 3, 4, 4) = 2

Реализация алгоритма

Функция solve(n, m, h, w) решает задачу для листа с размерами n и m, и конверта с размерами h и w.

long long solve(long long n, long long m, long long h, long long w)

{

if (h >= n && w >= m) return 0;

if (h < n) return 1 + solve(n, m, 2 * h, w);

return 1 + solve(n, m, h, 2 * w); // w < m

}

Основная часть программы. Читаем входные данные.

scanf("%lld %lld %lld %lld", &n, &m, &h, &w);

Вычисляем и выводим ответ.

printf("%lld\n", min(solve(n, m, h, w), solve(m, n, h, w)));

Python реализация

Функция solve(n, m, h, w) решает задачу для листа с размерами n и m, и конверта с размерами h и w.

def solve(n, m, h, w):

if h >= n and w >= m:

return 0

if h < n:

return 1 + solve(n, m, h * 2, w)

return 1 + solve(n, m, h, w * 2)

Основная часть программы. Читаем входные данные.

n, m, h, w = map(int, input().split())

Вычисляем и выводим ответ.

res = min(solve(n, m, h, w), solve(m, n, h, w))

print(res)